{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Magic Square"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestMagicSquare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大的幻方"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个 <code>k x k</code> 的<strong> 幻方</strong> 指的是一个 <code>k x k</code> 填满整数的方格阵，且每一行、每一列以及两条对角线的和 <strong>全部</strong><strong>相等</strong> 。幻方中的整数 <strong>不需要互不相同</strong> 。显然，每个 <code>1 x 1</code> 的方格都是一个幻方。</p>\n",
    "\n",
    "<p>给你一个 <code>m x n</code> 的整数矩阵 <code>grid</code> ，请你返回矩阵中 <strong>最大幻方</strong> 的 <strong>尺寸</strong> （即边长 <code>k</code>）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/29/magicsquare-grid.jpg\" style=\"width: 413px; height: 335px;\">\n",
    "<pre><b>输入：</b>grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>最大幻方尺寸为 3 。\n",
    "每一行，每一列以及两条对角线的和都等于 12 。\n",
    "- 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12\n",
    "- 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12\n",
    "- 对角线的和：5+4+3 = 6+4+2 = 12\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/29/magicsquare2-grid.jpg\" style=\"width: 333px; height: 255px;\">\n",
    "<pre><b>输入：</b>grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]\n",
    "<b>输出：</b>2\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-magic-square](https://leetcode.cn/problems/largest-magic-square/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-magic-square](https://leetcode.cn/problems/largest-magic-square/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]', '[[5,1,3,1],[9,3,3,1],[1,3,3,8]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        width = len(grid[0])\n",
    "        height = len(grid)\n",
    "\n",
    "        for i in reversed(range(1, min(height, width) + 1)):\n",
    "            for x in range(height-i+1):\n",
    "                for y in range(width-i+1):\n",
    "                    temp, flag = 0, 1\n",
    "                    left, right = 0, 0\n",
    "                    for r in range(i):\n",
    "                        row, col = 0, 0\n",
    "                        for c in range(i):\n",
    "                            col += grid[x+c][y+r]\n",
    "                            row += grid[x+r][y+c]\n",
    "                            if r == c:\n",
    "                                left += grid[x+r][y+c]\n",
    "                            if r+c == i-1:\n",
    "                                right += grid[x+r][y+c]\n",
    "                        if flag:\n",
    "                            flag = 0\n",
    "                            temp = row\n",
    "                        if temp != row or temp != col:\n",
    "                            temp = -1\n",
    "                            break\n",
    "                    if left == right == temp:\n",
    "                        return i\n",
    "        return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    h, w = 0, 0\n",
    "\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        self.h = len(grid)\n",
    "        self.w = len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(1, min(self.h, self.w)+1):\n",
    "            if self.hasMagic(grid, i):\n",
    "                res = i\n",
    "        return res\n",
    "\n",
    "    def hasMagic(self, grid, l):\n",
    "        for i in range(self.h-l+1):\n",
    "            for j in range(self.w-l+1):\n",
    "                if self.isMagic(grid, i, j, l):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    def isMagic(self, grid, r, c, l):\n",
    "        goal = sum(grid[r][c:c+l])\n",
    "        for i in range(r, r+l):\n",
    "            if sum(grid[i][c:c+l]) != goal:\n",
    "                return False\n",
    "        for j in range(c, c+l):\n",
    "            if sum(grid[k][j] for k in range(r, r+l)) != goal:\n",
    "                return False\n",
    "        if sum(grid[r+i][c+i] for i in range(l)) != goal:\n",
    "            return False\n",
    "        if sum(grid[r+i][c+l-i-1] for i in range(l)) != goal:\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        # 矩阵大小是50*50\n",
    "        # 暴力模拟，遍历幻方的大小，1-50 *幻方内元素\n",
    "        def check(x,y,c):\n",
    "            # 计算行\n",
    "            same = 0\n",
    "            for i in range(x-c+1,x+1):\n",
    "                sum_num = sum(grid[i][y-c+1:y+1])\n",
    "                if same == 0:\n",
    "                    same = sum_num\n",
    "                else:\n",
    "                    if same != sum_num:\n",
    "                        return False\n",
    "\n",
    "            # 计算列\n",
    "            for j in range(y-c+1,y+1):\n",
    "                sum_num = 0\n",
    "                for i in range(x-c+1,x+1):\n",
    "                    sum_num += grid[i][j]\n",
    "                if sum_num != same:\n",
    "                    return False \n",
    "            \n",
    "            # 计算对角线\n",
    "            sum_num = 0\n",
    "            for i in range(c):\n",
    "                sum_num += grid[x-i][y-i]\n",
    "            if sum_num != same:\n",
    "                return False\n",
    "\n",
    "            sum_num = 0\n",
    "            for i in range(c):\n",
    "                sum_num += grid[x-i][y-c+1+i]\n",
    "            if sum_num != same:\n",
    "                return False\n",
    "\n",
    "            return True \n",
    "        \n",
    "        for i in range(min(len(grid),len(grid[0]))+1,1,-1):\n",
    "            for x in range(i-1,len(grid)):\n",
    "                for y in range(i-1,len(grid[0])):\n",
    "                    if check(x,y,i):\n",
    "                        return i \n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        ans=1\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def cando(i,j,s):\n",
    "            last=0\n",
    "            for ii in range(size):\n",
    "                t = sum(grid[i+ii][j:j+s])\n",
    "                if last and t!=last:\n",
    "                    return False\n",
    "                else:\n",
    "                    last = t\n",
    "            for ii in range(size):\n",
    "                t = sum([grid[i+jj][j+ii] for jj in range(size)])\n",
    "                if last and t!=last:\n",
    "                    return False\n",
    "                else:\n",
    "                    last = t\n",
    "            t1,t2=0,0\n",
    "            for ii in range(size):\n",
    "                t1+=grid[i+ii][j+ii]\n",
    "                t2+=grid[i+ii][j+s-1-ii]\n",
    "            return t1==last and t2==last \n",
    "        for size in range(2, min(m,n)+1):\n",
    "            for x in range(0,m-size+1):\n",
    "                for y in range(0,n-size+1):\n",
    "                    if cando(x,y,size):\n",
    "                        ans=max(ans,size)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MatrixSum:\n",
    "    def __init__(self, matrix: List[List[int]]):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, x in enumerate(row):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + x\n",
    "        self.s = s\n",
    "\n",
    "    # 返回左上角在 (r1,c1) 右下角在 (r2-1,c2-1) 的子矩阵元素和（类似前缀和的左闭右开）\n",
    "    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:\n",
    "        return self.s[r2][c2] - self.s[r2][c1] - self.s[r1][c2] + self.s[r1][c1]\n",
    "\n",
    "    # 如果你不习惯左闭右开，也可以这样写\n",
    "    # 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和\n",
    "    def query2(self, r1: int, c1: int, r2: int, c2: int) -> int:\n",
    "        return self.s[r2 + 1][c2 + 1] - self.s[r2 + 1][c1] - self.s[r1][c2 + 1] + self.s[r1][c1]\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rowsum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        colsum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1]\n",
    "                colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1]\n",
    "\n",
    "        def check(x1, y1, x2, y2):\n",
    "            val = rowsum[x1 + 1][y2 + 1] - rowsum[x1 + 1][y1]\n",
    "            for i in range(x1 + 1, x2 + 1):\n",
    "                if rowsum[i + 1][y2 + 1] - rowsum[i + 1][y1] != val:\n",
    "                    return False\n",
    "            for j in range(y1, y2 + 1):\n",
    "                if colsum[x2 + 1][j + 1] - colsum[x1][j + 1] != val:\n",
    "                    return False\n",
    "            s, i, j = 0, x1, y1\n",
    "            while i <= x2:\n",
    "                s += grid[i][j]\n",
    "                i += 1\n",
    "                j += 1\n",
    "            if s != val:\n",
    "                return False\n",
    "            s, i, j = 0, x1, y2\n",
    "            while i <= x2:\n",
    "                s += grid[i][j]\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            if s != val:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        for k in range(min(m, n), 1, -1):\n",
    "            i = 0\n",
    "            while i + k - 1 < m:\n",
    "                j = 0\n",
    "                while j + k - 1 < n:\n",
    "                    i2, j2 = i + k - 1, j + k - 1\n",
    "                    if check(i, j, i2, j2):\n",
    "                        return k\n",
    "                    j += 1\n",
    "                i += 1\n",
    "        return 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        def is_fine(x: int, y: int, k: int) -> bool:\n",
    "            target = sum(grid[x][y:y+k])\n",
    "            # check row\n",
    "            for i in range(x, x + k):\n",
    "                row_sum = 0\n",
    "                for j in range(y, y + k):\n",
    "                    row_sum += grid[i][j]\n",
    "                if row_sum != target:\n",
    "                    return False\n",
    "            # check column\n",
    "            for j in range(y, y + k):\n",
    "                col_sum = 0\n",
    "                for i in range(x, x + k):\n",
    "                    col_sum += grid[i][j]\n",
    "                if col_sum != target:\n",
    "                    return False\n",
    "            \n",
    "            # diag\n",
    "            first_diag = 0\n",
    "            second_diag = 0\n",
    "            for d in range(k):\n",
    "                first_diag += grid[x + d][y + d]\n",
    "                # (x, y + k - 1) -> (x + d, y + k - 1 - d)\n",
    "                second_diag += grid[x + d][y + k - 1 -d]\n",
    "            print(first_diag, second_diag)\n",
    "            return first_diag == target and second_diag == target\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        k = min(n, m)\n",
    "        ans = None\n",
    "        while k > 0:\n",
    "            if ans is not None:\n",
    "                break\n",
    "            for i in range(n):\n",
    "                if ans is not None:\n",
    "                    break\n",
    "                for j in range(m):\n",
    "                    if i + k <= n and j + k <= m and is_fine(i, j, k):\n",
    "                        ans = k\n",
    "                        break\n",
    "            k -= 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        ans = 1\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def check(k):\n",
    "            for i in range(m - k + 1):\n",
    "                for j in range(n - k + 1):\n",
    "                    s = sum(grid[i][j:j + k])\n",
    "                    if not all(sum(grid[i0][j:j + k]) == s for i0 in range(i, i + k)):\n",
    "                        continue\n",
    "                    if not all(sum(col[i:i + k]) == s for col in list(zip(*grid))[j:j + k]):\n",
    "                        continue\n",
    "                    s0 = sum(grid[i + k0][j + k0] for k0 in range(k))\n",
    "                    s1 = sum(grid[i + k0][j + k - k0 - 1] for k0 in range(k))\n",
    "                    if s0 != s or s1 != s:\n",
    "                        continue\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        for k in range(min(m, n), 0, -1):\n",
    "            if check(k):\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        def checkMagicSquare(x, y, k):\n",
    "            sums = []\n",
    "            \n",
    "            # Check rows\n",
    "            for i in range(x, x + k):\n",
    "                sums.append(sum(grid[i][y:y+k]))\n",
    "                \n",
    "            # Check columns\n",
    "            for j in range(y, y + k):\n",
    "                sums.append(sum(grid[i][j] for i in range(x, x + k)))\n",
    "                \n",
    "            # Check diagonals\n",
    "            sums.append(sum(grid[x + i][y + i] for i in range(k)))\n",
    "            sums.append(sum(grid[x + i][y + k - 1 - i] for i in range(k)))\n",
    "            \n",
    "            # Return whether all sums are equal\n",
    "            return len(set(sums)) == 1\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for k in range(min(m, n), 1, -1):  # Start from the largest possible magic square size\n",
    "            for i in range(m - k + 1):\n",
    "                for j in range(n - k + 1):\n",
    "                    if checkMagicSquare(i, j, k):\n",
    "                        return k\n",
    "                        \n",
    "        return 1  # If no larger magic square found, return 1\n",
    "\n",
    "# Example\n",
    "# grid = [[7,1,4,5,6], [2,5,1,6,4], [1,5,4,3,2], [1,2,7,3,4]]\n",
    "# sol = Solution()\n",
    "# print(sol.largestMagicSquare(grid))  # This should return 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + grid[i][j]\r\n",
    "\r\n",
    "        def check(i:int, j:int, k:int) -> bool:\r\n",
    "                \r\n",
    "            a = [s[x + 1][j + 1] - s[x][j + 1] - s[x + 1][j - k + 1] + s[x][j - k + 1] for x in range(i - k + 1, i + 1)]\r\n",
    "            b = [s[i + 1][y + 1] - s[i + 1][y] - s[i - k + 1][y + 1] + s[i - k + 1][y] for y in range(j - k + 1, j + 1)]\r\n",
    "            s1 = sum(grid[x][i + j - k + 1 - x] for x in range(i - k + 1, i + 1))\r\n",
    "            s2 = sum(grid[x][x - i + j] for x in range(i - k + 1, i + 1))\r\n",
    "            return len(set(a + b + [s1, s2])) == 1\r\n",
    "            \r\n",
    "        for k in range(min(m, n), 1, -1):\r\n",
    "            for i in range(k -1, m):\r\n",
    "                for j in range(k - 1, n):\r\n",
    "                    if check(i, j, k):\r\n",
    "                        return k\r\n",
    "        return 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 1\n",
    "        rowsum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        colsum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1]\n",
    "                colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1]\n",
    "\n",
    "        def check(a, b, c, d):\n",
    "            lth = (c-a+1)\n",
    "            rows = [rowsum[i+1][d+1] - rowsum[i+1][b] for i in range(a+1, c+1)]\n",
    "            if len(set(rows)) != 1 : return False\n",
    "            cols = [colsum[c+1][i+1] - colsum[a][i+1] for i in range(b+1, d+1)]\n",
    "            if len(set(cols)) != 1 : return False\n",
    "            \n",
    "            diag1 = 0\n",
    "            diag2 = 0\n",
    "            for i in range(lth):\n",
    "                diag1 += grid[a+i][b+i]\n",
    "                diag2 += grid[a+i][d-i]\n",
    "            #     for j in range(lth):\n",
    "            #         x = grid[a+i][b+j]\n",
    "            #         rows[i] += x\n",
    "            #         cols[j] += x\n",
    "            #         if i == j:\n",
    "            #             diag1 += x\n",
    "            #         if i + j == lth - 1:\n",
    "            #             diag2 += x\n",
    "            return rows[0] == cols[0] == diag1 == diag2\n",
    "        \n",
    "   \n",
    "        for i in range(m):\n",
    "            if m-i <= ans: return ans\n",
    "            for j in range(n):\n",
    "                mx = min(m-i, n-j)\n",
    "                for k in range(mx, ans, -1):\n",
    "                    if check(i, j, i+k-1, j+k-1):\n",
    "                        ans = max(ans, k)\n",
    "                    \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    h, w = 0, 0\n",
    "    rowsum = []\n",
    "    colsum = []\n",
    "\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        self.h = len(grid)\n",
    "        self.w = len(grid[0])\n",
    "\n",
    "        self.rowsum = [[0] * self.w for _ in range(self.h)]\n",
    "        for i in range(self.h):\n",
    "            self.rowsum[i][0] = grid[i][0]\n",
    "            for j in range(1, self.w):\n",
    "                self.rowsum[i][j] = self.rowsum[i][j - 1] + grid[i][j]\n",
    "\n",
    "        self.colsum = [[0] * self.w for _ in range(self.h)]\n",
    "        for j in range(self.w):\n",
    "            self.colsum[0][j] = grid[0][j]\n",
    "            for i in range(1, self.h):\n",
    "                self.colsum[i][j] = self.colsum[i - 1][j] + grid[i][j]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, min(self.h, self.w)+1):\n",
    "            if self.hasMagic(grid, i):\n",
    "                res = i\n",
    "        return res\n",
    "\n",
    "    def hasMagic(self, grid, l):\n",
    "        for i in range(self.h-l+1):\n",
    "            for j in range(self.w-l+1):\n",
    "                if self.isMagic(grid, i, j, l):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    def isMagic(self, grid, r, c, l):\n",
    "        goal = self.rowsum[r][c+l-1] - (self.rowsum[r][c-1] if c > 0 else 0)\n",
    "        for i in range(r, r+l):\n",
    "            if self.rowsum[i][c+l-1] - (self.rowsum[i][c-1] if c > 0 else 0) != goal:\n",
    "                return False\n",
    "        for j in range(c, c+l):\n",
    "            if self.colsum[r+l-1][j] - (self.colsum[r-1][j] if r > 0 else 0) != goal:\n",
    "                return False\n",
    "        if sum(grid[r+i][c+i] for i in range(l)) != goal:\n",
    "            return False\n",
    "        if sum(grid[r+i][c+l-i-1] for i in range(l)) != goal:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        # 这个东西显然是没有单调性的，只能用前缀和优化一下\n",
    "        # 50 * 50 * 50 * 50 = 6.25 * 10^6 应该可以过\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pre_row = [list(accumulate(row, initial=0)) for row in grid]\n",
    "        pre_col = [list(accumulate(col, initial=0)) for col in zip(*grid)]\n",
    "        \n",
    "        max_k = 1\n",
    "        for r0 in range(m):\n",
    "            for c0 in range(n):\n",
    "                k_start = max_k\n",
    "                for k in range(k_start+1, 1+min(m, n)):\n",
    "                    r1 = r0 + k - 1\n",
    "                    c1 = c0 + k - 1\n",
    "                    if r1 >= m or c1 >= n:\n",
    "                        break\n",
    "                    v = pre_row[r0][c1+1] - pre_row[r0][c0]\n",
    "                    s = True\n",
    "\n",
    "                    for i in range(r0, 1 + r1):\n",
    "                        if pre_row[i][c1+1] - pre_row[i][c0] != v:\n",
    "                            s = False\n",
    "                            break\n",
    "                    if not s:\n",
    "                        continue\n",
    "\n",
    "                    for j in range(c0, 1+c1):\n",
    "                        if pre_col[j][r1+1] - pre_col[j][r0] != v:\n",
    "                            s = False\n",
    "                            break\n",
    "                    if not s:\n",
    "                        continue\n",
    "                    \n",
    "                    if sum(grid[r0+i][c0+i] for i in range(k)) != v:\n",
    "                        continue\n",
    "                    if sum(grid[r0+i][c1-i] for i in range(k)) != v:\n",
    "                        continue\n",
    "                    \n",
    "                    max_k = max(max_k, k)\n",
    "        \n",
    "        return max_k\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        r, c, dl, dr = copy.deepcopy(grid), copy.deepcopy(grid), copy.deepcopy(grid), copy.deepcopy(grid)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0:                c[i][j] = grid[i][j] + c[i-1][j]\n",
    "                if j - 1 >= 0:                r[i][j] = grid[i][j] + r[i][j-1]\n",
    "                if i - 1 >= 0 and j - 1 >= 0: dl[i][j] = grid[i][j] + dl[i-1][j-1]\n",
    "                if i - 1 >= 0 and j + 1 < n:  dr[i][j] = grid[i][j] + dr[i-1][j+1]\n",
    "\n",
    "        for k in range(min(m,n) - 1, 0, -1):\n",
    "            for i in range(m-k):\n",
    "                for j in range(n-k):\n",
    "                    dlsum = dl[i+k][j+k] - dl[i][j]  + grid[i][j]\n",
    "                    drsum = dr[i+k][j] - dr[i][j+k]  + grid[i][j+k]\n",
    "                    isMatch = dlsum == drsum \n",
    "                    ni, nj = i, j \n",
    "                    while ni <= i + k and isMatch:\n",
    "                        rowsum = r[ni][j+k] - r[ni][j] + grid[ni][j]\n",
    "                        isMatch = dlsum == rowsum\n",
    "                        ni += 1\n",
    "                    while nj <= j + k and isMatch:\n",
    "                        colsum = c[i+k][nj] - c[i][nj] + grid[i][nj]\n",
    "                        isMatch = dlsum == colsum\n",
    "                        nj += 1\n",
    "                    if isMatch:\n",
    "                        return k + 1\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        # 每一行的前缀和\n",
    "        rowsum = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            rowsum[i][0] = grid[i][0]\n",
    "            for j in range(1, n):\n",
    "                rowsum[i][j] = rowsum[i][j - 1] + grid[i][j]\n",
    "        \n",
    "        # 每一列的前缀和\n",
    "        colsum = [[0] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            colsum[0][j] = grid[0][j]\n",
    "            for i in range(1, m):\n",
    "                colsum[i][j] = colsum[i - 1][j] + grid[i][j]\n",
    "\n",
    "        # 从大到小枚举边长 edge\n",
    "        for edge in range(min(m, n), 1, -1):\n",
    "            # 枚举正方形的左上角位置 (i,j)\n",
    "            for i in range(m - edge + 1):\n",
    "                for j in range(n - edge + 1):\n",
    "                    # 计算每一行、列、对角线的值应该是多少（以第一行为样本）\n",
    "                    stdsum = rowsum[i][j + edge - 1] - (0 if j == 0 else rowsum[i][j - 1])\n",
    "                    check = True\n",
    "                    # 枚举每一行并用前缀和直接求和\n",
    "                    # 由于我们已经拿第一行作为样本了，这里可以跳过第一行\n",
    "                    for ii in range(i + 1, i + edge):\n",
    "                        if rowsum[ii][j + edge - 1] - (0 if j == 0 else rowsum[ii][j - 1]) != stdsum:\n",
    "                            check = False\n",
    "                            break\n",
    "                    if not check:\n",
    "                        continue\n",
    "                    \n",
    "                    # 枚举每一列并用前缀和直接求和\n",
    "                    for jj in range(j, j + edge):\n",
    "                        if colsum[i + edge - 1][jj] - (0 if i == 0 else colsum[i - 1][jj]) != stdsum:\n",
    "                            check = False\n",
    "                            break\n",
    "                    if not check:\n",
    "                        continue\n",
    "                    \n",
    "                    # d1 和 d2 分别表示两条对角线的和\n",
    "                    # 这里 d 表示 diagonal\n",
    "                    d1 = d2 = 0\n",
    "                    # 不使用前缀和，直接遍历求和\n",
    "                    for k in range(edge):\n",
    "                        d1 += grid[i + k][j + k]\n",
    "                        d2 += grid[i + k][j + edge - 1 - k]\n",
    "                    if d1 == stdsum and d2 == stdsum:\n",
    "                        return edge\n",
    "\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestMagicSquare(self, grid: list[list[int]]) -> int:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        # row_sum行前缀和\r\n",
    "        row_sum = [[0] * (n) for _ in range(m)]\r\n",
    "        for i in range(m):\r\n",
    "            row_sum[i][0] = grid[i][0]\r\n",
    "            for j in range(1, n):\r\n",
    "                row_sum[i][j] = row_sum[i][j-1] + grid[i][j]\r\n",
    "        # col_sum列前缀和\r\n",
    "        col_sum = [[0] * (m) for _ in range(n)]\r\n",
    "        for i in range(n):\r\n",
    "            col_sum[i][0] = grid[0][i]\r\n",
    "            for j in range(1, m):\r\n",
    "                col_sum[i][j] = col_sum[i][j-1] + grid[j][i]\r\n",
    "        # 行前缀和\r\n",
    "        # [[7, 8, 12, 17, 23], \r\n",
    "        # [2, 7, 8, 14, 18],\r\n",
    "        # [1, 6, 10, 13, 15], \r\n",
    "        # [1, 3, 10, 13, 17]]\r\n",
    "        # 列前缀和\r\n",
    "        #[[7, 9, 10, 11], \r\n",
    "        # [1, 6, 11, 13], \r\n",
    "        # [4, 5, 9, 16], \r\n",
    "        # [5, 11, 14, 17],\r\n",
    "        # [6, 10, 12, 16]]\r\n",
    "        # 检查是否为幻方\r\n",
    "        def check(i, j, k):\r\n",
    "            # 第一行的和\r\n",
    "            target = row_sum[i][j+k-1] - (row_sum[i][j-1] if j > 0 else 0)\r\n",
    "            # 检查行\r\n",
    "            for r in range(i, i+k):\r\n",
    "                # print(r,row_sum[r][j+k-1],row_sum[r][j-1],target)\r\n",
    "                if row_sum[r][j+k-1] - (row_sum[r][j-1] if j > 0 else 0) != target:\r\n",
    "                    return False\r\n",
    "            # 检查列\r\n",
    "            for c in range(j, j+k):\r\n",
    "                # print(c,col_sum[c][i+k-1],col_sum[c][i],target)\r\n",
    "                if col_sum[c][i+k-1] - (col_sum[c][i-1] if i > 0 else 0) != target:\r\n",
    "                    return False\r\n",
    "            # 检查对角线\r\n",
    "            if sum(grid[i+r][j+r] for r in range(k)) != target:\r\n",
    "                return False\r\n",
    "            if sum(grid[i+r][j+k-1-r] for r in range(k)) != target:\r\n",
    "                return False\r\n",
    "            return True\r\n",
    "        # 枚举位置和边长\r\n",
    "        for k in range(min(m, n), 0, -1):\r\n",
    "            for i in range(m-k+1):\r\n",
    "                for j in range(n-k+1):\r\n",
    "                    if check(i, j, k):\r\n",
    "                        return k\r\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMagicSquare(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        row_matrix = [[0]*(n+2) for _ in range(m+1)]\n",
    "        col_matrix = [[0]*(n+2) for _ in range(m+1)]\n",
    "        angle_matrix = [[0]*(n+2) for _ in range(m+1)]\n",
    "        anti_matrix = [[0]*(n+2) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                row_matrix[i+1][j+1] = row_matrix[i+1][j] + grid[i][j]\n",
    "                col_matrix[i+1][j+1] = col_matrix[i][j+1] + grid[i][j]\n",
    "                angle_matrix[i+1][j+1] = angle_matrix[i][j] + grid[i][j]\n",
    "                anti_matrix[i+1][j+1] = anti_matrix[i][j+2] + grid[i][j]\n",
    "\n",
    "        def check(size):\n",
    "            print(size)\n",
    "            for i in range(m-size+1):\n",
    "                for j in range(n-size+1):\n",
    "                    sm = row_matrix[i+1][j+size] - row_matrix[i+1][j]\n",
    "                    flag = True\n",
    "                    for r in range(i+1, i+size):\n",
    "                        if sm != row_matrix[r+1][j+size] - row_matrix[r+1][j]:\n",
    "                            flag = False \n",
    "                            break\n",
    "\n",
    "                    if not flag:\n",
    "                        continue\n",
    "\n",
    "                    for c in range(j,j+size):\n",
    "                        if sm != col_matrix[i+size][c+1] - col_matrix[i][c+1]:\n",
    "                            flag = False \n",
    "                            break\n",
    "\n",
    "                    if not flag:\n",
    "                        continue\n",
    "\n",
    "                    if not sm == angle_matrix[i+size][j+size] - angle_matrix[i][j] == anti_matrix[i+size][j+1] - anti_matrix[i][j+size+1]:\n",
    "                        continue\n",
    "\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        for size in range(min(m,n), 1,-1):\n",
    "            if check(size):\n",
    "                return size\n",
    "\n",
    "\n",
    "        return 1\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
